{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Score by Changing Two Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #修改两个元素的最小分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums</code> 的 <strong>最小</strong>&nbsp;得分是满足 <code>0 &lt;= i &lt; j &lt; nums.length</code>&nbsp;的&nbsp;<code>|nums[i]&nbsp;- nums[j]|</code>&nbsp;的最小值。</li>\n",
    "\t<li><code>nums</code>的 <strong>最大 </strong>得分是满足 <code>0 &lt;= i &lt; j &lt; nums.length</code>&nbsp;的&nbsp;<code>|nums[i]&nbsp;- nums[j]|</code>&nbsp;的最大值。</li>\n",
    "\t<li><code>nums</code>&nbsp;的分数是 <strong>最大</strong>&nbsp;得分与 <strong>最小</strong>&nbsp;得分的和。</li>\n",
    "</ul>\n",
    "\n",
    "<p>我们的目标是最小化&nbsp;<code>nums</code>&nbsp;的分数。你 <strong>最多</strong> 可以修改&nbsp;<code>nums</code>&nbsp;中&nbsp;<strong>2</strong>&nbsp;个元素的值。</p>\n",
    "\n",
    "<p>请你返回修改&nbsp;<code>nums</code>&nbsp;中&nbsp;<strong>至多两个</strong>&nbsp;元素的值后，可以得到的 <strong>最小分数</strong>&nbsp;。</p>\n",
    "\n",
    "<p><code>|x|</code>&nbsp;表示 <code>x</code>&nbsp;的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,4,3]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。<code>|nums[i] - nums[j]|</code> 的值永远为 0 ，所以我们返回 0 + 0 = 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,4,7,8,5]\n",
    "<b>输出：</b>3\n",
    "<b>解释：\n",
    "</b>将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。\n",
    "最小得分是 i = 0 且 j = 1 时得到的 |<code>nums[i] - nums[j]</code>| = |6 - 6| = 0 。\n",
    "最大得分是 i = 3 且 j = 4 时得到的 |<code>nums[i] - nums[j]</code>| = |8 - 5| = 3 。\n",
    "最大得分与最小得分之和为 3 。这是最优答案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-score-by-changing-two-elements](https://leetcode.cn/problems/minimum-score-by-changing-two-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-score-by-changing-two-elements](https://leetcode.cn/problems/minimum-score-by-changing-two-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,3]', '[1,4,7,8,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        return min(nums[n-1] - nums[2], nums[n-2] - nums[1], nums[n-3] - nums[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-1]-nums[2],nums[-3]-nums[0],nums[-2] - nums[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        # min( abs(nums[i]-nums[j]) + abs(nums[k]-nums[l]) )\n",
    "        if len(nums) == 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-2]-nums[1], nums[-1]-nums[2], nums[-3]-nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        cand1 = nums[-3] - nums[0]\n",
    "        cand2 = nums[-2] - nums[1]\n",
    "        cand3 = nums[-1] - nums[2]\n",
    "        return min(cand1, cand2, cand3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[2], nums[-3] - nums[0], nums[-2] - nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        # 将两个最值改为相同的数，最小得分就变为0了\n",
    "        # 问题是，改最大值还是最小值？\n",
    "        # 第二大和第二小的绝对差\n",
    "        # 第三大和最小的绝对差\n",
    "        # 第三小和最大的绝对差\n",
    "        # 返回以上3者中的最小值\n",
    "        nums.sort()\n",
    "        return min(nums[-2] - nums[1], nums[-1] - nums[2], nums[-3] - nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-2] - nums[1], nums[-3] - nums[0], nums[-1] - nums[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res1 = nums[-3] - nums[0]\n",
    "        res2 = nums[-2] - nums[1]\n",
    "        res3 = nums[-1] - nums[2]\n",
    "\n",
    "        res = min(res1,res2,res3)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-1]-nums[2],nums[-2]-nums[1],nums[-3]-nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        max_val = min(nums[-3] - nums[0], nums[-1] - nums[2])\n",
    "        \n",
    "        res = max_val\n",
    "        n = len(nums)\n",
    "        tmp = nums[-2] - nums[1]\n",
    "        res = min(tmp, res)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        return min(nums[i-3] - nums[i] for i in range(3))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min([nums[-1]-nums[2],nums[-2]-nums[1],nums[-3]-nums[0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-2] - nums[1], nums[-1] - nums[2], nums[-3] - nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        max_score = min(nums[-2] - nums[1], nums[-1] - nums[2], nums[-3] - nums[0])\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-3] - nums[0], nums[-2] - nums[1], nums[-1] - nums[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        if l <= 3:\n",
    "            return 0\n",
    "        else:\n",
    "            return min(x for x in [nums[-1] - nums[2], nums[l - 3] - nums[0], nums[l - 2] - nums[1]])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-3] - nums[0], nums[-2] - nums[1], nums[-1] - nums[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-3]-nums[0],nums[-2]-nums[1],nums[-1]-nums[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[2], nums[-3] - nums[0], nums[-2] - nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeSum(self, nums: list[int]) -> int:\r\n",
    "        if len(nums) <= 3:\r\n",
    "            return 0\r\n",
    "        else:\r\n",
    "            num_list = sorted(nums)\r\n",
    "            answer1 = num_list[-2] - num_list[1]\r\n",
    "            answer2 = num_list[-3] - num_list[0]\r\n",
    "            answer3 = num_list[-1] - num_list[2]\r\n",
    "        return min(answer1, answer2, answer3)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        #print(nums)\n",
    "        k0 = nums[-2] - nums[1]\n",
    "        k1 = nums[-3] - nums[0]\n",
    "        k2 = nums[-1] - nums[2] \n",
    "        \n",
    "        #调整\n",
    "        res = min(k0,k1,k2)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        n1 = nums[-3] - nums[0]\n",
    "        n2 = nums[-1] - nums[2]\n",
    "        n3 = nums[-2] - nums[1]\n",
    "        return min(n1, n2, n3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        #最小得分为0\n",
    "        #先排序\n",
    "        nums.sort()\n",
    "        return min(nums[-3]-nums[0],nums[-2]-nums[1],nums[-1]-nums[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        排序 + 分类谈论\n",
    "        1.修改最大的两个数为 第3大的数字 最小得分=0, 最大得分=nums[n-3] - nums[0]\n",
    "        2.修改最小的两个数为 第3小的数字 最小得分=0, 最大得分=nums[n-1] - nums[2]\n",
    "        3.修改最小的这个数和最大的这个数 为第2大的数字 最小得分=0, 最大得分=nums[n-2] - nums[1]\n",
    "    '''\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n == 3: return 0\n",
    "        ans = inf\n",
    "        ans = min(ans, nums[n - 3] - nums[0])\n",
    "        ans = min(ans, nums[n - 1] - nums[2])\n",
    "        ans = min(ans, nums[n - 2] - nums[1])\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[2], nums[-2] - nums[1], nums[-3] - nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        return min(a[-3] - a[0], a[-2] - a[1], a[-1] - a[2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[-3]- nums[0], nums[-2]-nums[1],nums[-1]-nums[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        cand1 = nums[-3] - nums[0]\n",
    "        cand2 = nums[-2] - nums[1]\n",
    "        cand3 = nums[-1] - nums[2]\n",
    "        return min(cand1, cand2, cand3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "            nums[i]-nums[j]  最小值 \n",
    "            nums[i]- nums[j]  最大值\n",
    "\n",
    "            说明与 顺序无关   因此 数组必然可以排序\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        return min(nums[-3]-nums[0],nums[-2]-nums[1],nums[-1]-nums[2])\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        # 在可改变元素值的情况下，最小差值一定为0，本题关键就是找到最大差值的最小情况\n",
    "        nums.sort()\n",
    "        a = nums[-1] - nums[2] # 最大值不变\n",
    "        b = nums[-3] - nums[0] # 最小值不变\n",
    "        c = nums[-2] - nums[1] # 最大值最小值都改变\n",
    "        temp = min(a, b)\n",
    "        return min(temp, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 3:\n",
    "            return 0\n",
    "\n",
    "        nums = sorted(nums)\n",
    "        v = []\n",
    "        for i in range(1, len(nums)):\n",
    "            v.append(abs(nums[i]-nums[i-1]))\n",
    "\n",
    "        ret = sum(v)\n",
    "        min_val = 0\n",
    "        min_val = max(min_val, v[0]+v[1])\n",
    "        min_val = max(min_val, v[0]+v[-1])\n",
    "        min_val = max(min_val, v[-2]+v[-1])\n",
    "\n",
    "        \n",
    "\n",
    "        return sum(v)-min_val\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
